// 给定一个可包含重复数字的序列 nums ，按序列内字典升序返回所有不重复的全排列。
// 其中序列内字典升序指的是， 序列内从左到右的非降序排列，例如 nums=[1,2,3], 则因为[1,2,3] < [1,3,2], [3,1,2] < [3,2,1]， [1,2,3]要先于[1,3,2]输出，[3,1,2]要先于[3,2,1]输出


#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型vector<vector<>>
     */
    vector<vector<int>> res;
    vector<vector<int> > UniquePerm(vector<int>& nums) {
        // write code here
        sort(nums.begin(),nums.end());
        unordered_map<int,bool> hash;
        for(auto i:nums){
            hash[i]=false;
        }
        vector<int> vec;
        int cnt=0;
        int len=nums.size();
        dfs(hash,nums,vec,cnt,len);
        return res;
    }

    void dfs(unordered_map<int,bool>& hash,vector<int>& nums,vector<int>& vec,int& cnt,int& len){
        while(true){
            if(cnt>len){
                if(find(res.begin(),res.end(),vec)==res.end()){
                    res.emplace_back(vec);
                }
                return;
            }
            ++cnt;
            int i;
            for(i=0;i<nums.size();++i){
                if(hash[nums[i]]==false){
                    vec.emplace_back(nums[i]);
                    hash[nums[i]]=true;
                    break;
                }
            }
            dfs(hash,nums,vec,cnt,len);
            hash[nums[i]]=false;
            vec.erase(vec.begin()+vec.size()-1);
            --cnt;
        }
    }
};